package leetcode101_xqzhao

// TODO 组合总和 【-】 递归+回溯

func combinationSum(candidates []int, target int) [][]int {
	n := len(candidates)
	res := make([][]int, 0)
	path := make([]int, 0)

	var dfs039 func(strat int, nums []int, sum int)
	dfs039 = func(start int, nums []int, sum int) {
		// 递归结束控制器
		if sum > target {
			return
		}
		// 保存结果
		if sum == target {
			newTmp := make([]int, len(path))
			// 这里注意一定要使用 copy, 不然后续对 path 的修改会影响结果中 保存的数据
			copy(newTmp, path)
			res = append(res, newTmp)
		}
		// 递归执行
		for i := start; i < n; i++ {
			path = append(path, candidates[i])
			dfs039(i, nums, sum+nums[i])
			// 回溯
			path = path[:len(path)-1]
		}
	}

	dfs039(0, candidates, 0)
	return res
}
